/**
 * 
 */
package array.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class SpiralMatrix {

	/**
	Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

	For example,
	Given the following matrix:

	[
	[ 1, 2, 3 ],
	[ 4, 5, 6 ],
	[ 7, 8, 9 ]
	]

	You should return [1,2,3,6,9,8,7,4,5].
	 */
	public ArrayList<Integer> spiralOrder(int[][] matrix) {
		// Start typing your Java solution below
		// DO NOT write main() function
		ArrayList<Integer> result = new ArrayList<Integer>();
		if (matrix != null && matrix.length > 0)
			spiralOrder(matrix, matrix.length, matrix[0].length, 0, result);
		return result;
	}

	public void spiralOrder(int[][] matrix, int rows, int cols, int level,
			ArrayList<Integer> result) {
		if (rows <= 0 || cols <= 0) {
			return;
		}

		if (rows == 1) {
			for (int i = 0; i < cols; i++) {
				result.add(matrix[level][level + i]);
			}
			return;
		}
		if (cols == 1) {
			for (int i = 0; i < rows; i++) {
				result.add(matrix[level + i][level]);
			}
			return;
		}
		// top 
		for (int i = 0; i < cols - 1; i++)
			result.add(matrix[level][level + i]);
		// right
		for (int i = 0; i < rows - 1; i++)
			result.add(matrix[level + i][level + cols - 1]);
		//bottom
		for (int i = cols - 1; i > 0; i--)
			result.add(matrix[level + rows - 1][level + i]);
		// left
		for (int i = rows - 1; i > 0; i--)
			result.add(matrix[level + i][level]);

		spiralOrder(matrix, rows - 2, cols - 2, level + 1, result);
	}

	/**
	 * 
	 */
	public SpiralMatrix() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SpiralMatrix sm = new SpiralMatrix();
		int[][] matrix = new int[0][0];
		sm.spiralOrder(matrix);

	}

}
